// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 中心自由列表。
// 
// 有关概述，请参见malloc.go。
// 
// mcentral实际上不包含自由对象列表；mspan有。
// 每个mcentral是两个MSPAN列表：具有自由对象的列表（c->nonempty）
// 和完全分配的列表（c->empty）。

package runtime

import "runtime/internal/atomic"

// 给定大小的自由对象的中心列表。
// 
// go:notinheap 
type mcentral struct {
	spanclass spanClass

	// 部分和全部包含两个mspan集：一个在用扫掠
	// 跨距，一个在用未扫掠跨距。这两个角色在每个GC循环中交换
	// 角色。未扫描集由
	// 分配或在每个GC循环中由后台清理程序
	// 排出，因此只需要两个角色。
	// 
	// 在每个GC循环中，扫描的
	// 跨距为部分[sweepgen/2%2]，未扫描的跨距为
	// 部分[1-sweepgen/2%2]。扫掠从
	// 未扫掠集弹出跨距，并推送仍在
	// 扫掠集上使用的跨距。同样，分配正在使用的范围会将其推到扫描集上的
	// 上。
	// 
	// 扫掠器的某些部分可以扫掠任意跨距，因此
	// 无法将其从未扫掠集中删除，但会将跨距
	// 添加到相应的扫掠列表中。因此，
	// 扫掠器和mcentral中使用未扫掠列表的部分可能会遇到扫掠跨距，应忽略这些跨距。
	partial [2]spanSet // 有自由对象的跨区列表
	full    [2]spanSet // 没有自由对象的跨区列表
}

// 初始化单个中心自由列表。
func (c *mcentral) init(spc spanClass) {
	c.spanclass = spc
	lockInit(&c.partial[0].spineLock, lockRankSpanSetSpine)
	lockInit(&c.partial[1].spineLock, lockRankSpanSetSpine)
	lockInit(&c.full[0].spineLock, lockRankSpanSetSpine)
	lockInit(&c.full[1].spineLock, lockRankSpanSetSpine)
}

// partialUnswept返回保存此扫描根的部分填充
// 未扫描跨距的跨距集。
func (c *mcentral) partialUnswept(sweepgen uint32) *spanSet {
	return &c.partial[1-sweepgen/2%2]
}

// partialSwept返回保存部分填充的
// 此扫描根的扫描跨度的跨度集。
func (c *mcentral) partialSwept(sweepgen uint32) *spanSet {
	return &c.partial[sweepgen/2%2]
}

// FULLUNSWEEPT返回不包含任何
// 此扫描根可用插槽的未扫描跨距的跨距集。
func (c *mcentral) fullUnswept(sweepgen uint32) *spanSet {
	return &c.full[1-sweepgen/2%2]
}

// FULLSWEED返回保存扫描跨距的跨距集，该跨距集不包含此扫描生成器的任何
// 空闲插槽。
func (c *mcentral) fullSwept(sweepgen uint32) *spanSet {
	return &c.full[sweepgen/2%2]
}

// 分配要在McCache中使用的范围。
func (c *mcentral) cacheSpan() *mspan {
	// 如有必要，扣除此范围分配和扫描的信用。
	spanBytes := uintptr(class_to_allocnpages[c.spanclass.sizeclass()]) * _PageSize
	deductSweepCredit(spanBytes, 0)

	traceDone := false
	if trace.enabled {
		traceGCSweepStart()
	}

	// 如果我们在扫描预算跨度时没有找到任何可用的
	// 空间，只需分配一个新的跨度即可。这限制了我们花在寻找可用空间上的时间量，并分摊了小对象覆盖整个可用空间的成本。通过将其设置为100，我们将空间开销限制为1%。
	// 
	// TODO（奥斯汀，mknyszek）：这仍然有糟糕的最坏情况
	// 吞吐量。例如，在第100个扫描跨距上只能找到一个空闲插槽
	// 。这限制了分配延迟，但
	// 的吞吐量仍然很低。相反，我们可以让
	// 免费运行到已使用的预算，如果预算较低，则切换到新的span 
	// 分配。
	spanBudget := 100

	var s *mspan
	sl := newSweepLocker()
	sg := sl.sweepGen

	// 首先尝试部分扫描跨距。
	if s = c.partialSwept(sg).pop(); s != nil {
		goto havespan
	}

	// 现在尝试部分未拉伸跨距。
	for ; spanBudget >= 0; spanBudget-- {
		s = c.partialUnswept(sg).pop()
		if s == nil {
			break
		}
		if s, ok := sl.tryAcquire(s); ok {
			// 我们已经获得了span的所有权，所以让我们扫描它并使用它。
			s.sweep(true)
			sl.dispose()
			goto havespan
		}
		// 我们未能获得span的所有权，这意味着它正在或
		// 已被异步清理程序清理，无法将其从未清理列表中删除
		// 。该清理者拥有span和
		// 的所有权，负责将其释放到堆中或将其放在
		// 右清理列表中。不管怎样，我们都应该忽略它（对我们来说做任何其他事情都是不安全的）。
	}
	// 现在尝试完整的未拉伸跨距，如果无法获得跨距，则将其扫掠并将其放入
	// 正确的列表中。
	for ; spanBudget >= 0; spanBudget-- {
		s = c.fullUnswept(sg).pop()
		if s == nil {
			break
		}
		if s, ok := sl.tryAcquire(s); ok {
			// 我们拥有了span的所有权，所以让我们打扫一下。
			s.sweep(true)
			// 检查是否有可用空间。
			freeIndex := s.nextFreeIndex()
			if freeIndex != s.nelems {
				s.freeindex = freeIndex
				sl.dispose()
				goto havespan
			}
			// 将其添加到扫描列表中，因为扫描没有给我们任何可用空间。
			c.fullSwept(sg).push(s.mspan)
		}
		// 部分未拉伸跨距见注释。
	}
	sl.dispose()
	if trace.enabled {
		traceGCSweepDone()
		traceDone = true
	}

	// 我们无法从mcentral获取span，因此请从mheap获取一个span。
	s = c.grow()
	if s == nil {
		return nil
	}

	// 此时s是一个应该有空闲插槽的跨距。
havespan:
	if trace.enabled && !traceDone {
		traceGCSweepDone()
	}
	n := int(s.nelems) - int(s.allocCount)
	if n == 0 || s.freeindex == s.nelems || uintptr(s.allocCount) == s.nelems {
		throw("span has no free objects")
	}
	freeByteBase := s.freeindex &^ (64 - 1)
	whichByte := freeByteBase / 8
	// 初始化所有位缓存。
	s.refillAllocCache(whichByte)

	// 调整Allocache，使s.freeindex对应于
	// s.allocache中的低位。
	s.allocCache >>= s.freeindex % 64

	return s
}

// 来自McCache的返回范围。
// 
// s必须有一个与此
// mcentral对应的span类，并且不能为空。
func (c *mcentral) uncacheSpan(s *mspan) {
	if s.allocCount == 0 {
		throw("uncaching span but s.allocCount == 0")
	}

	sg := mheap_.sweepgen
	stale := s.sweepgen == sg+1

	// 安装sweepgen。
	if stale {
		// Span在扫描开始前已缓存。清扫它是我们的责任。
		// 
		// 设置sweepgen以指示它未被缓存，但需要
		// 扫描，无法从中分配。sweep将
		// 设置s.sweepgen以指示s已扫描。
		atomic.Store(&s.sweepgen, sg-1)
	} else {
		// 表示不再缓存s。
		atomic.Store(&s.sweepgen, sg)
	}

	// 将跨度放在适当的位置。
	if stale {
		// 它已经过时了，所以只要扫一扫就行了。清扫将把它放在
		// 正确的列表上。
		// 
		// 我们这里不使用清扫柜。陈旧的缓存跨区
		// 不在全局扫描列表中，因此标记终止
		// 本身会延迟扫描完成，直到所有MCache 
		// 都已扫描完毕。
		ss := sweepLocked{s}
		ss.sweep(false)
	} else {
		if int(s.nelems)-int(s.allocCount) > 0 {
			// 将其放回部分扫描列表。
			c.partialSwept(sg).push(s)
		} else {
			// 没有可用空间，也没有过时，因此请将其放在
			// 完整扫描列表中。
			c.fullSwept(sg).push(s)
		}
	}
}

// grow从堆中分配一个新的空跨度，并为c的size类初始化它。
func (c *mcentral) grow() *mspan {
	npages := uintptr(class_to_allocnpages[c.spanclass.sizeclass()])
	size := uintptr(class_to_size[c.spanclass.sizeclass()])

	s, _ := mheap_.alloc(npages, c.spanclass, true)
	if s == nil {
		return nil
	}

	// 使用乘除和移位快速计算：
	// n:=（npages<<u PageShift）/size 
	n := s.divideByElemSize(npages << _PageShift)
	s.limit = s.base() + size*n
	heapBitsForAddr(s.base()).initSpan(s)
	return s
}
